#include "SecondPhase.hpp"

int SecondPhase::run() {
    // Job distribution. How can this be done? Each item has to be assigned to
    // a CPU to be mined. This can be done dynamically or just by dividing the 
    // reduced counts hash into roughly equal parts. The latter is used here.
    
    /*********************** debug **************************
    // Let's see how we handled the transactions.
    // fpTree.printHeaderTable();
    printHeaderVector();
    ************************ debug *************************/ 

    // This is the start (and the end) of everything. -tayfunsen
    clock_t start = clock();
    mine();
    if (Globals::verbose)
        cout << "Rank " << Globals::rank << ": Mine finished -\t"
            << (clock() - start) / double (CLOCKS_PER_SEC) << " s." << endl;
        

    /************************ debug *************************/
    // cout << "End mine() for rank: " << rank << endl;
    // cout << "Starting printing the local result tree, for rank: " << rank << endl;
    // resultTree.print(outputFileName);
    // cout << "End printing the local result tree, for rank: " << rank <<
    //    endl;
    /************************ debug *************************/ 

    // Send local result trees to each other.
    start = clock();
#ifdef USE_MPI
    if (Globals::reduceBroadcast)
        reduceAndBcastResults();
    else
        all_reduce(world, resultTree, mergedResult, reduce_result_trees());
#else
    mergedResult = resultTree;
#endif
    // We don't need resultTree anymore. Clear it. 
    resultTree.makeEmpty();

    if (Globals::verbose) {
        cout << "Rank " << Globals::rank << ": Result trees reduced -\t"
             << (clock() - start) / double (CLOCKS_PER_SEC) << " s." << endl;
    }

    // Print merged results. For rank 0 only.
    if (Globals::rank == 0) {
        start = clock();
        mergedResult.print(Globals::outputFileName);
        if (Globals::verbose)
            cout << "Rank " << Globals::rank << ": Result tree printed -\t"
                << (clock() - start) / double (CLOCKS_PER_SEC) << " s." << endl;
    }
}

void SecondPhase::mine() {
    Prefix prefix;
    // We do not ensure having a branch computed in a single node, that would
    // be costly. But we try to work on such an ordering that if an item is
    // computed later than another one, it is not lower in the tree than the
    // latter. ie. it might be higher on the same branch or it might be totally
    // on another branch altogether.
    vector<HeaderInfo *>::reverse_iterator it = startIt;
    for (int i = 0; i < partSize; i++) {
        projectTree(prefix, *it, fpTree, NULL);
        it++;
    }
}

// This is the actual mining method.
// The node * argument should always be at a lower level than the root.
// CAUTION: The Tree argument for below function should at no times be modified.
// ie. It is functionally a const value.
int SecondPhase::projectTree(Prefix prefix, HeaderInfo * hi, Tree & t, Tree * pt) {
    // Item skipping technique
    if (pt != NULL && t.getItemCount(hi->item) == pt->getItemCount(hi->item)) {
        // support count in the parent tree is the same as the current one.
        pt->skipHeaderInfo(hi->item);
    }
    if (hi->skip)
        return 0;

    Node * node = hi->first;
    hash_map<string, int> itemCounts;
    vector< vector<string> *> transactions;

    /************ data types defined for this loop *********************/
    // "Node * current" will be used for traversing side links, Node *temp 
    // will be used for traversing up the tree.
    /************ data types defined for this loop *********************/
    Node * current = node;
    int hasSideLinks = 0;
    for ( ; ; ) {
        // Reserve place for the transaction.
        vector<string> * transaction = new vector<string>;
        int count = current->getCount();
        Node * temp = current;

        for ( ; ; ) {
            // Will use parent to go up the tree. Stop if root is reached.
            temp = temp->getParent();
            string item = temp->getItem();
            if (item == "root")
                break;
            transaction->push_back(item);
            itemCounts[item] += count;
        }

        transactions.push_back(transaction);

        // Will use side links to traverse between nodes with the same item.
        // See if there are side links.
        current = current->getNext();
        if (current == NULL)
            break;
        hasSideLinks = 1;
    }

    /************ debug *****************************************************
    cout << "Before pruning:" << endl;
    printTransactions(transactions);
    ************ debug *****************************************************/

    // We have computed transactions for a prefix. Update prefix to reflect 
    // this.
    string item = node->getItem();
    prefix.addWithCount(item, t.getItemCount(item));
    // We should now prune transactions according to minimum item counts.
    pruneTransactions(transactions, itemCounts);

    /************ debug *****************************************************
    cout << "After pruning, but before sorting:" << endl;
    printTransactions(transactions);
    ************ debug *****************************************************/

    // Inserting to the result tree. If there is one conditional database for
    // this prefix, than you can merge them and finish here. No need to mine
    // recursively. item merging technique.
    if (!hasSideLinks) {
        if (node->getCount() >= Globals::minimumSupport) {
            // Merge prefix and the transaction. Item merging technique.
            vector<string>::iterator it = prefix.items.begin(), end = prefix.items.end();
            vector<string> * transactionP = *(transactions.begin());
            for ( ; it != end; it++) {
                transactionP->push_back(*it);
            }

            // Sort the transaction according to the *global* item counts.
            sort((*(transactions.begin()))->begin(), (*(transactions.begin()))->end(), SortingFunctor(&globalCounts));

            // Insertion to a result tree representing frequent itemsets is 
            // different from insertion to an fp-tree which represents transactions.
            resultTree.insert(transactions[0], node->getCount());
        }
        return 0;
    }

    // Sort the transactions:
    vector< vector<string> * >::iterator it = transactions.begin(), 
        end = transactions.end();
    for ( ; it != end; it++) {
        // While inserting to the projected tree, you do not use global counts
        // for sorting, but local item counts.
        sort((*it)->begin(), (*it)->end(), SortingFunctor(&itemCounts));
    }

    /************ debug *****************************************************
    cout << "After sorting:" << endl;
    printTransactions(transactions);
    ************ debug *****************************************************/

    // Insert each transaction to a new fp tree. This will make up projected 
    // tree.
    Tree pTree;
    current = node;
    it = transactions.begin(), end = transactions.end();
    for ( ; it != end; it++, current = current->getNext()) {
        pTree.insert(*it, current->getCount());
    }
    // Also add the item counts to the tree.
    pTree.setItemCounts(itemCounts);

    // Projected fp tree has been finished. For each item in header vector of
    // the new tree call the projectTree method recursively with the 
    // HeaderInfo * and the prefix.
    vector<HeaderInfo *>::reverse_iterator hvIt = (pTree.getHeaderVector()).rbegin(), hvEnd = (pTree.getHeaderVector()).rend();
    for ( ; hvIt != hvEnd; hvIt++) {
        // Sub-itemset pruning technique implemented here.
        if (resultTree.subItemsetPruning(prefix))
            continue;
        projectTree(prefix, *hvIt, pTree, &t);
    }
    // In the end insert the prefix to the result tree as well, since this is 
    // also a potential frequent item list.
    if (prefix.count >= Globals::minimumSupport) {
        sort(prefix.items.begin(), prefix.items.end(), SortingFunctor(&globalCounts));
        resultTree.insert(&prefix.items, prefix.count);
    }

    return 0;
}

#ifdef USE_MPI
void SecondPhase::reduceAndBcastResults() {
    // Let root be 0.
    int master = 0;
    reduce(world, resultTree, mergedResult, reduce_result_trees(), master);
    // Send reduced results to everyone else.
    broadcast(world, mergedResult, master);      
}
#endif

// This method removes items with lower than minimum support from transactions.
void SecondPhase::pruneTransactions(vector< vector<string> * > & transactions, 
        hash_map<string, int> & itemCounts) {
    vector< vector<string> * >::iterator it = transactions.begin(),
        end = transactions.end();

    for ( ; it != end; it++) {
        vector<string>::iterator trIt = (*it)->begin(),
            trEnd = (*it)->end();

        // If the current item's count is less than min. count, erase it.      
        for (int i = 0; trIt != trEnd; i++) {
            if (itemCounts[*trIt] < Globals::minimumSupport) {
                trIt = (*it)->erase(trIt); // trIt++ idi. tayfunsen
                trEnd = (*it)->end();
            }
            else
                trIt++;
        }
    }
}

void SecondPhase::printHeaderVector() {
    cout << "Header Vector for rank: " << Globals::rank <<
        " printed in the order to be mined." << endl;

    vector<HeaderInfo *>::reverse_iterator rit = startIt;
    for (int i = 0; i < partSize; i++) {
        cout << (*rit)->item << ", ";
        rit++;
    }
    
    cout << endl << "Finished printing header vector for rank: " <<
        Globals::rank << endl;

    cout << "Printing the whole header vector: " << endl;
    vector<HeaderInfo *>::iterator it = fpTree.getHeaderVector().begin(),
        end = fpTree.getHeaderVector().end();
    for ( ; it != end; it++) {
        cout << (*it)->item << ", ";
    }
    cout << "Finished printing the whole header vector. " << endl;
}

// Prints transactions. For debugging purposes.
void SecondPhase::printTransactions(vector< vector<string> *> transactions) {
    vector< vector<string> *>::iterator it = transactions.begin(), 
        end = transactions.end();

    for ( ; it != end; it++) {
        vector<string>::iterator trIt = (*it)->begin(),
            trEnd = (*it)->end();

        for ( ; trIt != trEnd; trIt++) {
            cout << *trIt << ", ";
        }

        cout << endl;
    }
}

